package LimitedTimeGame.Day_0210;

/**
 * @author zxc
 * @date 2023/02/10 10:12
 **/

import java.util.*;

/**
 * 题目 ：二维网格迁移
 * 题目详述 ：
 * 给你一个 m 行 n列的二维网格grid和一个整数k。你需要将grid迁移k次。
 * 每次「迁移」操作将会引发下述活动：
 * 位于 grid[i][j]的元素将会移动到grid[i][j + 1]。
 * 位于grid[i][n- 1] 的元素将会移动到grid[i + 1][0]。
 * 位于 grid[m- 1][n - 1]的元素将会移动到grid[0][0]。
 * 请你返回k 次迁移操作后最终得到的 二维网格。
 *
 * 提示：
 * m ==grid.length
 * n ==grid[i].length
 * 1 <= m <= 50
 * 1 <= n <= 50
 * -1000 <= grid[i][j] <= 1000
 * 0 <= k <= 100
 *
 */
public class ShiftGrid {
    public static void main(String[] args) {
        int[][] temp = {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(shiftGrid(temp, 1));
    }
    /**
     * 思路 ：
     * 即，依赖于双端队列的特性
     * （1）首先，将grid数组中所有元素加入到deque双端队列中;
     * （2）其次，对于双端队列弹出k个尾部元素，同时将所弹出的尾部元素加入到deque头部;
     * （3）最后，从双端队列deque头部开始遍历，直至全部遍历结束 && 使用list集合，来存储指定结果;
     * @param grid
     * @param k
     * @return
     */
    public static List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int len = grid.length;
        int col = grid[0].length;
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();
        // 将grid数组中所有元素加入到deque双端队列中
        for(int i = 0 ; i < len ; i++){
            for(int j = 0 ; j < col ; j++){
                deque.offer(grid[i][j]);
            }
        }
        // 对于双端队列弹出k个尾部元素，同时将所弹出的尾部元素加入到deque头部
        while(k > 0){
            deque.offerFirst(deque.removeLast());
            k--;
        }
        // 从双端队列deque头部开始遍历，直至全部遍历结束 && 使用list集合，来存储指定结果
        for(int i = 0 ; i < len * col ; i += col){
            List<Integer> list = new ArrayList<>();
            for(int j = 0 ; j < col ; j++){
                list.add(deque.removeFirst());
            }
            result.add(list);
        }
        // 返回结果集合;
        return result;
    }
}
